//class Solution {
//public:
//    int maxTurbulenceSize(vector<int>& arr) {
//        int n = arr.size();
//        vector<int> f(n, 1);
//        auto g = f;
//        for (int i = 1; i < n; i++)
//        {
//            if (arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;
//            if (arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;
//        }
//        int ret1 = 0, ret2 = 0;
//        for (auto e : f) ret1 = max(ret1, e);
//        for (auto e : g) ret2 = max(ret2, e);
//        return max(ret1, ret2);
//    }
//};

//class Solution {
//public:
//    bool wordBreak(string s, vector<string>& wordDict) {
//        unordered_set<string> hash;
//        for (auto e : wordDict) hash.insert(e);
//        int n = s.size();
//        vector<bool> dp(n + 1, false);
//        dp[0] = true;
//        s = ' ' + s;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = i; j >= 1; j--)
//            {
//                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
//                {
//                    dp[i] = true;
//                    break;
//                }
//            }
//        }
//        return dp[n];
//    }
//};

//class Solution {
//public:
//    int findSubstringInWraproundString(string s) {
//        int n = s.size();
//        vector<int> dp(n, 1);
//        for (int i = 1; i < n; i++)
//        {
//            if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
//                dp[i] += dp[i - 1];
//        }
//        int hash[26] = { 0 };
//        for (int i = 0; i < n; i++)
//        {
//            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
//        }
//        int sum = 0;
//        for (int i = 0; i < 26; i++)
//        {
//            sum += hash[i];
//        }
//        return sum;
//    }
//};

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;


//class Solution {
//public:
//    int longestConsecutive(vector<int>& nums) {
//        int n = nums.size();
//        sort(nums.begin(), nums.end());
//        set<int> se(nums.begin(), nums.end());
//        vector<int> arr(se.begin(), se.end());
//        n = arr.size();
//        int left = 0, right = 0, len = 0;
//        while (right < n)
//        {
//            right++;
//            len = max(len, right - left);
//            if (right < n && arr[right] - arr[right - 1] != 1)
//            {
//                left = right;
//            }
//        }
//        return len;
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<int> nums = { 100,4,200,1,3,2 };
//    int ret = s.longestConsecutive(nums);
//    cout << ret << endl;
//    return 0;
//
//}


